package leetcode.weekly.week340;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

//Solution4Test
public class Solution6 {

	int m, n;
	int[][] grid;

	public int minimumVisitedCells(int[][] grid) {
		m = grid.length;
		n = grid[0].length;
		if (0 == m - 1 && 0 == n - 1) {
			return 1;
		}
		this.grid = grid;
//		for(int i)
		Set<Long> been = new HashSet<>();
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { 0, 0, 1 });
		been.add(index(0, 0));
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int x = cur[0], y = cur[1], cnt = cur[2];
			int size = this.grid[x][y];
			for (int i = Math.min(y + size, n - 1); i >= y + 1; i--) {
				if (x == m - 1 && i == n - 1) {
					return cnt + 1;
				}
				if (this.grid[x][i] == 0) {
					continue;
				}
				long to = this.index(x, i);
				if (been.contains(to)) {
					break;
				}

				queue.add(new int[] { x, i, cnt + 1 });
			}
			for (int i = Math.min(x + size, m - 1); i >= x + 1; i--) {
				if (i == m - 1 && y == n - 1) {
					return cnt + 1;
				}
				if (this.grid[i][y] == 0) {
					continue;
				}
				long to = this.index(x, i);
				if (been.contains(to)) {
					break;
				}

				queue.add(new int[] { i, y, cnt + 1 });
			}
		}
		return -1;
	}

	public long index(int i, int j) {
		return i * n + j;
	}

}
